import java.util.HashMap;
import java.util.Map;

public class Solution1373 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    Map<TreeNode,int[]> map=new HashMap<>();
    int ans=0;

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root==null){
            return;
        }
        dfs(root.left);
        dfs(root.right);
        int k1=root.left==null?0:map.get(root.left)[3];
        int k2=root.right==null?0:map.get(root.right)[3];
        boolean b= (root.left==null || (map.get(root.left)[0]==1 && map.get(root.left)[2]<root.val)) && (root.right==null || (map.get(root.right)[0]==1 && map.get(root.right)[1]>root.val));
        if (b){
            map.put(root,new int[]{1,root.left==null?root.val:map.get(root.left)[1],root.right==null?root.val:map.get(root.right)[2],root.val+k1+k2});
            ans=Math.max(ans,root.val+k1+k2);
        }else {
            map.put(root,new int[]{0,-1,-1,-1});
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1373().maxSumBST(new TreeNode(9,new TreeNode(2,null,new TreeNode(2,new TreeNode(3,new TreeNode(-5,null,new TreeNode(1)),new TreeNode(4,null,new TreeNode(10))),null)),new TreeNode(3))));
    }
}
